package com.blb.suanfa;

/**
 * 排序算法
 */
public class SortDemo {

    /**
     * 冒泡排序 O(n2)
     * N个数字来排队，两两相比小靠前，外层循环n-1，内层循环n-1-i
     * @param array
     */
    public static void burbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    /**
     * 插入排序 O(n2)
     * @param array
     */
    public static void insertSort(int[] array){
        //从第二个数开始，选择插入数
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            //把前面每个数和插入数进行比较，比插入数大就向后移动
            int j;
            for(j = i;j > 0 && array[j - 1] > temp;j--){
                array[j] = array[j - 1];
            }
            //最后j就是比插入数小的位置，将插入数插入
            array[j] = temp;
        }
    }

    /**
     * 选择排序 O(n2)
     * 找最小值和数组第一个进行交换
     * 找第二小和数组第二个进行交换
     * ...
     * @param array
     */
    public static void selectSort(int[] array){
        //控制找最小值的范围
        for (int i = 0; i < array.length; i++) {
            int min = i;
            //找最小值的位置
            for(int j = i;j < array.length;j++){
                if(array[j] < array[min]){
                    min = j;
                }
            }
            //最小值和开头的数交换
            if(min != i){
                int temp = array[min];
                array[min] = array[i];
                array[i] = temp;
            }
        }
    }

    /**
     * 求基准数的位置
     */
    public static int pivot(int[] array,int start,int end){
        //定义左右两个下标
        int left = start;
        int right = end;
        //基准数默认为左下标
        int pivot = left;
        //如果左右下标没有重合，继续找
        while(left < right){
            //如果右下标的数比基准数大或相等，就往左移动
            while (left < right && array[right] >= array[pivot]){
                right--;
            }
            //如果左下标的数比基准数小或相等，就向右移动
            while(left < right && array[left] <= array[pivot]){
                left++;
            }
            //移动完后如果左下标小于右下标，交换左右下标的数
            if(left < right){
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
        //左右下标重合后，和基准数的元素进行交换，将重合下标作为新的基准数
        int temp = array[left];
        array[left] = array[pivot];
        array[pivot] = temp;
        return left;
    }

    /**
     * 快排 O(nlogn)
     */
    public static void quickSort(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        //获得基准数
        int pivot = pivot(array, start, end);
        //对前半部分递归
        quickSort(array,start,pivot - 1);
        //对后半部分递归
        quickSort(array,pivot + 1,end);
    }

    public static void main(String[] args) {
        int[] arr = {77,33,2,88,1,89,19};
//        burbleSort(arr);
//        selectSort(arr);
        quickSort(arr,0,arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
